/**
 * Created with IntelliJ IDEA.
 * Description:除自身以外数组的乘积
 * User: bjc
 * Date: 2025-11-19
 * Time: 10:32
 */
public class Test04_productExceptSelf {
    public int[] productExceptSelf(int[] nums) {
        //构造两个数组，用来记录i之前的前缀乘积，以及i之后的后缀乘积
        int n = nums.length;
        int[] ldp = new int[n];
        int[] rdp = new int[n];
        ldp[0] = 1;
        rdp[n - 1] = 1;
        int[] ret = new int[n];
        //前缀数组
        for (int i = 1; i < n; i++) {
            ldp[i] = ldp[i - 1] * nums[i - 1];
        }
        //后缀数组
        for (int i = n - 2; i >= 0; i--) {
            rdp[i] = rdp[i + 1] * nums[i + 1];
        }
        //遍历
        for (int i = 0; i < n; i++) {
            ret[i] = ldp[i] * rdp[i];
        }
        return ret;
    }
}
